home *** CD-ROM | disk | FTP | other *** search
/ Language/OS - Multiplatform Resource Library / LANGUAGE OS.iso / t3_1 / doc.lha / documentation / manual / evaluator.mss < prev    next >
Text File  |  1987-06-30  |  11KB  |  280 lines
  1. @part[EVALUATOR, root "TMAN.MSS"]       @comment{ -*-Mode:T;System:TMAN-*-}
  2. @appendix[A meta-circular evaluator]
  3. @label[EvaluatorAppendix]               @comment{ semantics chapter }
  4.  
  5. This appendix gives an annotated listing of an evaluator for @Tau[].
  6. This evaluator is written in @Tau[] (thus the adjective
  7. @qu"meta-circular," since it employs the notation it tries to
  8. describe) and attempts to continue in the spirit of @cite[STEELE78ART]
  9. and @cite[MCCARTHY60].  It represents an attempt, short of writing a
  10. denotational semantics, to provide a moderately precise description of
  11. @Tau[]'s semantics.
  12. @index[Evaluation]
  13.  
  14. This interpreter should also be of some interest simply as an extended
  15. example of a program written in @Tau[].
  16.  
  17. It is important to know what this evaluator is not:
  18. @begin[itemize]
  19. It is not efficient.  It expressly makes no effort at all to do things in
  20. clever or efficient ways.
  21.  
  22. It is not complete.  It tries to define most of the special forms that
  23. it uses, but does not define any primitive procedures such as @tc[CAR]
  24. or @tc[APPLY].  However, any special forms that have been omitted are,
  25. for the most part, trivially definable in terms of the special forms
  26. here defined, as source-to-source transformations; in fact this is the
  27. how the existing implementation works.
  28.  
  29. It is not parameterized (that is, extensible).  No means of passing in
  30. syntax tables or adding syntactic extensions (@tc[DEFINE-SYNTAX])
  31. is provided.
  32.  
  33. It makes no attempt to detect or deal with error conditions, such as
  34. unevaluable expressions, unbound variables, or wrong number of arguments
  35. in calls.
  36. @end[itemize]
  37.  
  38. @begin[group]
  39. @tc[EVALUATE], the universal function, computes the value of an
  40. expression in a given variable environment.  It dispatches to
  41. a specialist routine on the basis of the syntax of the expression.
  42.  
  43. @begin[TEG]
  44. (DEFINE (EVALUATE EXP ENV)
  45.   (COND ((SYMBOL? EXP)
  46.          (VALUE EXP ENV))
  47.         ((OR (NUMBER? EXP)
  48.              (CHARACTER? EXP)
  49.              (STRING? EXP))
  50.          EXP)
  51.         ((PAIR? EXP)
  52.          (CASE (CAR EXP)
  53.            ((QUOTE)    (EVALUATE-QUOTE    EXP ENV))
  54.            ((IF)       (EVALUATE-IF       EXP ENV))
  55.            ((BLOCK)    (EVALUATE-BLOCK    EXP ENV))
  56.            ((LAMBDA)   (EVALUATE-LAMBDA   EXP ENV))
  57.            ((DEFINE)   (EVALUATE-DEFINE   EXP ENV))
  58.            ((LSET)     (EVALUATE-LSET     EXP ENV))
  59.            ((SET)      (EVALUATE-SET      EXP ENV))
  60.            ((OBJECT)   (EVALUATE-OBJECT   EXP ENV))
  61.            ((LOCALE)   (EVALUATE-LOCALE   EXP ENV))
  62.            ((LOCATIVE) (EVALUATE-LOCATIVE EXP ENV))
  63.            ((COND)     (EVALUATE-COND     EXP ENV))
  64.            ((AND)      (EVALUATE-AND      EXP ENV))
  65.            ((OR)       (EVALUATE-OR       EXP ENV))
  66.            ((LET)      (EVALUATE-LET      EXP ENV))
  67.            (ELSE       (EVALUATE-CALL     EXP ENV))))))
  68. @end[TEG]
  69. @end[group]
  70.  
  71. @tc[EVALUATE-CALL] computes the value of a call to a procedure.
  72. The procedure and arguments are evaluated recursively, and the procedure
  73. is invoked using @tc[APPLY] (assumed to be primitive; not defined by this
  74. Appendix).
  75.  
  76. @begin[TEG]
  77. (DEFINE (EVALUATE-CALL EXP ENV)
  78.   (APPLY (EVALUATE (CAR EXP) ENV)
  79.          (MAP (LAMBDA (ARG) (EVALUATE ARG ENV))
  80.               (CDR EXP))))
  81. @end[TEG]
  82.  
  83. @tc[QUOTE], @tc[IF], and @tc[BLOCK] have straightforward definitions.
  84.  
  85. @begin[TEG]
  86. (DEFINE (EVALUATE-QUOTE EXP ENV)
  87.   (CADR EXP))
  88.  
  89. (DEFINE (EVALUATE-IF EXP ENV)
  90.   (IF (EVALUATE (CADR EXP) ENV)
  91.       (EVALUATE (CADDR EXP) ENV)
  92.       (EVALUATE (CADDDR EXP) ENV)))
  93.  
  94. (DEFINE (EVALUATE-BLOCK EXP ENV)
  95.   (EVALUATE-SEQUENCE (CDR EXP) ENV))
  96. @end[TEG]
  97.  
  98. @tc[EVALUATE-SEQUENCE] is an auxiliary routine called in several places.
  99. It needs to be careful to maintain tail-recursive semantics; thus the
  100. loop termination when @wt[(NULL? (CDR EXPS))] instead of the more
  101. obvious @wt[(NULL? EXPS)].
  102.  
  103. @begin[TEG]
  104. (DEFINE (EVALUATE-SEQUENCE EXPS ENV)
  105.   (COND ((NULL? (CDR EXPS))
  106.          (EVALUATE (CAR EXPS) ENV))
  107.         (ELSE
  108.          (EVALUATE (CAR EXPS) ENV)
  109.          (EVALUATE-SEQUENCE (CDR EXPS) ENV))))
  110. @end[TEG]
  111.  
  112. Surprisingly, @tc[EVALUATE-LAMBDA] has a very straightforward definition
  113. in terms of @tc[LAMBDA]: it simply returns a procedure which evaluates
  114. the body of the lambda-expression in an appropriately augmented variable
  115. environment.
  116.  
  117. @begin[TEG]
  118. (DEFINE (EVALUATE-LAMBDA EXP ENV)
  119.   (LAMBDA ARGS
  120.     (EVALUATE-SEQUENCE (CDDR EXP)
  121.                        (BIND-VARIABLES (CADR EXP) ARGS ENV))))
  122. @end[TEG]
  123.  
  124. @tc[SET] has two cases; whereas assignment to a variable must be
  125. primitive, assignment to a generalized @qu"place" is performed using a
  126. simple source-code rewrite.
  127.  
  128. @begin[TEG]
  129. (DEFINE (EVALUATE-SET EXP ENV)
  130.   (LET ((PLACE (CADR EXP)))
  131.     (COND ((ATOM? PLACE)
  132.            (SET-VALUE PLACE ENV (EVALUATE (CADDR EXP) ENV) NIL))
  133.           (ELSE
  134.            (EVALUATE `((SETTER ,(CAR PLACE)) ,@@(CDR PLACE) ,(CADDR EXP))
  135.                      ENV)))))
  136. @end[TEG]
  137.  
  138. @wt[(SET @i[variable value])] and @wt[(LSET @i[variable value])] are
  139. interpreted in exactly the same way, except for the fourth argument
  140. passed to @tc[SET-VALUE], which is a flag to be eventually passed to
  141. @tc[ENV-LOOKUP]; this determines whether the lookup proceeds outwards
  142. past the innermost locale, or stops there, where the variable is either
  143. replaced or inserted in the environment.  @tc[DEFINE] is the same as
  144. @tc[LSET], but permits extended syntax for defining procedures.
  145.  
  146. @begin[TEG]
  147. (DEFINE (EVALUATE-LSET EXP ENV)
  148.   (SET-VALUE (CADR EXP) ENV (EVALUATE (CADDR EXP) ENV) T))
  149.  
  150. (DEFINE (EVALUATE-DEFINE EXP ENV)
  151.   (LET ((PATTERN (CADR EXP)))
  152.     (COND ((ATOM? PATTERN)
  153.            (EVALUATE-LSET EXP ENV))
  154.           (ELSE
  155.            (EVALUATE-LSET `(LSET ,(CAR PATTERN)
  156.                                  (LAMBDA ,(CDR PATTERN) ,@@(CDDR EXP)))
  157.                           ENV)))))
  158. @end[TEG]
  159.  
  160. The evaluator implements @tc[OBJECT] using @tc[JOIN] by
  161. iteratively constructing, one method-clause at a time, an object which
  162. will have the requisite behavior.
  163. The auxiliary routine @tc[EVALUATE-OBJECT-AUX] could have been defined
  164. using @tc[LABELS], but the code would have become too deeply indented,
  165. exacerbating this manual's already forbidding formatting problems.
  166.  
  167. @begin[TEG]
  168. (DEFINE (EVALUATE-OBJECT EXP ENV)
  169.   (EVALUATE-OBJECT-AUX (EVALUATE (CADR EXP) ENV) (CDDR EXP) ENV))
  170.  
  171. (DEFINE (EVALUATE-OBJECT-AUX PROC CLAUSES ENV)
  172.   (COND ((NULL? CLAUSES)
  173.          (OBJECT PROC))
  174.         (ELSE
  175.          (LET ((CLAUSE (CAR CLAUSES)))
  176.            (JOIN (OBJECT PROC
  177.                          (((EVALUATE (CAAR CLAUSE) ENV) SELF . ARGS)
  178.                           (EVALUATE-SEQUENCE (CDR CLAUSE)
  179.                                              (BIND-VARIABLES (CDAR CLAUSE)
  180.                                                              (CONS SELF ARGS)
  181.                                                              ENV))))
  182.                  (EVALUATE-OBJECT-AUX NIL (CDR CLAUSES) ENV))))))
  183. @end[TEG]
  184.  
  185. As described elsewhere in this manual, a locale is an environment whose
  186. list of bound variables can be mutated, in a controlled way, as a
  187. side-effect.@index[locales]  To accomplish this, @tc[LOCALE] is
  188. implemented using a local variable @tc[THE-ENV] which is assigned new
  189. values (using a @tc[SET] side-effect) as new variables are added to the
  190. environment.  This happens whenever a locative for a variable is needed
  191. and cannot be located, either because the enclosing environment has no
  192. binding for the variable or because the @tc[LOCAL?] argument to
  193. @tc[ENV-LOOKUP] is true and the lookup must stop at the level of the
  194. locale.
  195.  
  196. The actual locale object has a trivial definition for the
  197. @tc[ENV-LOOKUP] method which jumps directly to whatever the current
  198. value of @tc[THE-ENV] happens to be.
  199.  
  200. @begin[TEG]
  201. (DEFINE (EVALUATE-LOCALE EXP ENV)
  202.   (LET ((THE-ENV NIL))
  203.     (SET THE-ENV
  204.          (OBJECT NIL
  205.                  ((ENV-LOOKUP SELF ID LOCAL? CREATE?)
  206.                   (COND ((AND LOCAL? (NOT CREATE?))
  207.                          NIL)
  208.                         ((AND (NOT LOCAL?)
  209.                               (ENV-LOOKUP ENV ID NIL NIL)))
  210.                         (CREATE?
  211.                          (SET THE-ENV
  212.                               (BIND-VARIABLE ID (UNDEFINED-VALUE) THE-ENV))
  213.                          (ENV-LOOKUP THE-ENV ID LOCAL? CREATE?))
  214.                         (ELSE NIL)))))
  215.     (LET ((THE-LOCALE
  216.            (OBJECT NIL
  217.                    ((ENV-LOOKUP SELF ID LOCAL? CREATE?)
  218.                     (ENV-LOOKUP THE-ENV ID LOCAL? CREATE?)))))
  219.       (IF (CADR EXP) (SET-VALUE (CADR EXP) THE-LOCALE THE-LOCALE T))
  220.       (EVALUATE-SEQUENCE (CDDR EXP) THE-LOCALE))))
  221. @end[TEG]
  222.  
  223. Environments are represented as objects which handle the @tc[ENV-LOOKUP]
  224. operation.  When a
  225. procedure created by @tc[LAMBDA] is called, @tc[BIND-VARIABLES] is
  226. called to build up a new environment structure, one variable at a time.
  227. This is analogous to the association-list technique used in
  228. @cite[STEELE78ART] and @cite[MCCARTHY60], except that the environment is
  229. represented not by list structure but by chained closure (i.e. object)
  230. structure.  (Compare this with the code for dynamic binding in
  231. @cite[STEELE76IMP], section 3.2.2.)
  232.  
  233. @tc[BIND-VARIABLES] is a simple recursion over the lists of formal and
  234. actual parameters, calling @tc[BIND-VARIABLE] for each variable which
  235. needs to be bound.  If the list of formals is an improper list then the
  236. identifier which is its last cdr must be bound to a list of the rest of
  237. the arguments.
  238.  
  239. @begin[TEG]
  240. (DEFINE (BIND-VARIABLES FORMALS ACTUALS ENV)
  241.   (COND ((PAIR? FORMALS)
  242.          (BIND-VARIABLE (CAR FORMALS)
  243.                         (CAR ACTUALS)
  244.                         (BIND-VARIABLES (CDR FORMALS)
  245.                                         (CDR ACTUALS)
  246.                                         ENV)))
  247.         ((NULL? FORMALS)
  248.          ENV)
  249.         (ELSE
  250.          (BIND-VARIABLE FORMALS ACTUALS ENV))))
  251.  
  252. (DEFINE (BIND-VARIABLE IDENTIFIER VALUE ENV)
  253.   (OBJECT NIL
  254.           ((ENV-LOOKUP SELF ID LOCAL? CREATE?)
  255.            (COND ((EQ? ID IDENTIFIER)
  256.                   (LOCATIVE VALUE))
  257.                  (ELSE
  258.                   (ENV-LOOKUP ENV ID LOCAL? CREATE?))))))
  259. @end[TEG]
  260.  
  261. Fetching and storing the value of a variable is accomplished by
  262. obtaining a locative to the variable using the @tc[ENV-LOOKUP]
  263. operation, and then either examining or depositing into the locative.
  264.  
  265. @begin[TEG]
  266. (DEFINE (VALUE ID ENV)
  267.   (CONTENTS (ENV-LOOKUP ENV ID NIL NIL)))
  268.  
  269. (DEFINE (SET-VALUE ID ENV VAL LOCAL?)
  270.   (SET (CONTENTS (ENV-LOOKUP ENV ID LOCAL? T)) VAL))
  271. @end[TEG]
  272.  
  273. @tc[EVALUATE-LOCATIVE], @tc[EVALUATE-COND], @tc[EVALUATE-OR],
  274. @tc[EVALUATE-AND], @tc[EVALUATE-CASE], and @tc[EVALUATE-LET] have been
  275. omitted to save space; their definitions are uninteresting.  Each
  276. could be done either as a primitive (@qu"fexpr"), as e.g. @tc[IF]
  277. is defined above, or could be done using source-to-source
  278. transformations (macros), using backquote and a single call to
  279. @tc[EVALUATE].
  280.